import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-09-12
 * Time: 23:30
 */
public class find_Substring {
    public static List<Integer> findSubstring(String str, String[] words) {

        List<Integer> ret=new ArrayList<>();

        int l = words[0].length();

        HashMap<String, Integer> words_hash = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            int n = words_hash.getOrDefault(words[i], 0);
            words_hash.put(words[i], n + 1);
        }




        for (int first = 0; first < l; first++) {

            int count =0;
            HashMap<String,Integer> string_hash =new HashMap<>();


            for (int right = first, left = first; right <= str.length()-l; right += l) {
                //进窗口
                String right_word= str.substring(right,right+l);
                int df =string_hash.getOrDefault(right_word,0);
                string_hash.put(right_word,df+1);
                if (words_hash.containsKey(right_word)){
                    if (df+1<=words_hash.get(right_word)){
                        count++;
                    }
                }
                if (right-left+l>words.length*l){
                    //判断
                    String left_word=str.substring(left,left+l);
                    int pop=string_hash.get(left_word);
                    //出窗口
                    if (words_hash.containsKey(left_word)){
                        if (pop<=words_hash.get(left_word)){
                            count--;
                        }
                    }
                    string_hash.put(left_word,pop-1);
                    left+=l;
                }
                if (count==words.length){
                    ret.add(left);
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        String s = "wordgoodgoodgoodbestword";
        String[] strings={"word","good","best","good"};
        System.out.println(findSubstring(s, strings));
    }
}
